package com.practice.niuke.new_direct_basics.class07;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 输入：
 * 正数数组costs
 * 正数数组profits
 * 正数k
 * 正数m
 * 含义：
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 * k表示你只能串行的最多做k个项目
 * m表示你初始的资金
 * 说明：
 * 你每做完一个项目， 马上获得的收益， 可以支持你去做下一个项目。
 * 输出：
 * 你最后获得的最大钱数。
 */
public class Code05_IPO {

    /**
     * 项目
     */
    public static class Node {
        // 利润
        public int p;
        // 花费
        public int c;

        public Node(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    /**
     * 比较器：
     * 以每个项目的花费进行比较，花费小的排在前面
     */
    public static class MinCostComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.c - o2.c;
        }

    }

    /**
     * 比较器：
     * 以每个项目的利润进行比较，利润大的排在前面
     */
    public static class MaxProfitComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o2.p - o1.p;
        }

    }

    /**
     * 最后获得的最大钱数
     *
     * @param k 总共可以做多少个项目
     * @param W 初始启动资金（目前手上有的资金）
     * @param Profits 项目列表的利润数组
     * @param Capital 项目列表的花费数组
     * @return int
     */
    public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        // 以项目花费 组成的 项目 小根堆（代表被锁住的项目）
        PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
        // 以项目利润 组成的 项目 大根堆（代表解锁的项目）
        PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
        // 所有项目扔到被锁池（代表被锁住项目的小根堆）中, 花费组织的小根堆
        for (int i = 0; i < Profits.length; i++) {
            minCostQ.add(new Node(Profits[i], Capital[i]));
        }
        for (int i = 0; i < k; i++) { // 进行K轮
            // 能力所及（花费小于等于目前手上有的资金）的项目，全解锁(从小根堆弹出压入大根堆中)
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
                maxProfitQ.add(minCostQ.poll());
            }
            // 目前手头上的本金不足以解锁任何项目
            if (maxProfitQ.isEmpty()) {
                return W;
            }
            // 从（装有解锁项目的）大根堆中弹出一个利润最大的项目做，
            // 将做这个项目得到的利润加入到本金中。
            W += maxProfitQ.poll().p;
        }
        return W;
    }

}
